{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Make the Integer Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #brainteaser"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #脑筋急转弯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeTheIntegerZero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到整数零需要执行的最少操作数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数：<code>num1</code> 和 <code>num2</code> 。</p>\n",
    "\n",
    "<p>在一步操作中，你需要从范围&nbsp;<code>[0, 60]</code> 中选出一个整数 <code>i</code> ，并从 <code>num1</code> 减去 <code>2<sup>i</sup> + num2</code> 。</p>\n",
    "\n",
    "<p>请你计算，要想使 <code>num1</code> 等于 <code>0</code> 需要执行的最少操作数，并以整数形式返回。</p>\n",
    "\n",
    "<p>如果无法使 <code>num1</code> 等于 <code>0</code> ，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num1 = 3, num2 = -2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>可以执行下述步骤使 3 等于 0 ：\n",
    "- 选择 i = 2 ，并从 3 减去 2<sup>2</sup> + (-2) ，num1 = 3 - (4 + (-2)) = 1 。\n",
    "- 选择 i = 2 ，并从 1 减去 2<sup>2</sup> + (-2) ，num1 = 1 - (4 + (-2)) = -1 。\n",
    "- 选择 i = 0 ，并从 -1 减去 2<sup>0</sup>&nbsp;+ (-2) ，num1 = (-1) - (1 + (-2)) = 0 。\n",
    "可以证明 3 是需要执行的最少操作数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num1 = 5, num2 = 7\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>可以证明，执行操作无法使 5 等于 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num1 &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= num2 &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-make-the-integer-zero](https://leetcode.cn/problems/minimum-operations-to-make-the-integer-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-make-the-integer-zero](https://leetcode.cn/problems/minimum-operations-to-make-the-integer-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n-2', '5\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        if num1 < num2: return -1\n",
    "        k = 0\n",
    "        while True:\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k\n",
    "            k += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "num1-k*num2 用二进制数字表示\n",
    "对这个数字观察，如果集合大小小于等于k的话，那么是可以的，直接就能够找到了\n",
    "如果集合大小大于k的话，那么肯定是不行的\n",
    "\n",
    "补充：数字小于k也是不可能的\n",
    "\n",
    "那么考虑k最多会是多少呢？考虑到，k的增长是线性的，集合大小的增长是很慢的。所以k不会很大，差不多就几十而已。\n",
    "\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x=num1-num2*k\n",
    "            #这里是因为num1是正数，而k是从1开始枚举的。所以如果x<k,就说明num2>0,那么对于更大的k，x无法变得更大\n",
    "            if x<k:return -1\n",
    "            if k>=x.bit_count(): return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        i = 0\n",
    "        while num1 - num2 > i:\n",
    "            i += 1\n",
    "            num1 -= num2\n",
    "            if num1.bit_count() <= i:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        #copy 0x3\n",
    "        for k in count(1):\n",
    "            x = num1-num2*k\n",
    "            if x<k:\n",
    "                return -1\n",
    "            if k>=x.bit_count():\n",
    "                return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        \n",
    "        for k in range(1,100):\n",
    "            x=num1-num2*k\n",
    "            if x<k:return -1\n",
    "            if k>=x.bit_count():return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        ans = -1\n",
    "        for i in range(61):\n",
    "            if num1-num2*i >= i and (num1-num2*i).bit_count() <= i:\n",
    "                ans = i\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        # 看num1 减去 多少个 num2之后，和可以是由同等数量的2的次方表示的数的和\n",
    "        if num1 <= num2: return -1\n",
    "        # 只要num1 - num2 大于0，一定存在解，只是如何找到最少的次数\n",
    "        k = 0\n",
    "        while True:\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k\n",
    "            k += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x=num1-num2*k\n",
    "            if x<k:return -1\n",
    "            if k>=x.bit_count():return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        def cnt(i):\n",
    "            ans = 0\n",
    "            b = bin(i)[2:]\n",
    "            for j in b:\n",
    "                if j == '1': ans += 1\n",
    "            return ans\n",
    "        def check(mid):\n",
    "            t = num1 - num2 * mid\n",
    "            if t < mid: return False\n",
    "            return cnt(t) <= mid\n",
    "        for i in range(1, 100):\n",
    "            if check(i):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        def check(s, step):\n",
    "            if s > 0 :\n",
    "                b = str(bin(s))[2:]\n",
    "            else:\n",
    "                b = str(bin(s))[3:]\n",
    "            c = Counter(b)\n",
    "            one = c[\"1\"]\n",
    "            zero = c[\"0\"]\n",
    "            if step >= one and step <= s:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        s = num1\n",
    "        step = 0\n",
    "        while s < 2**61 :\n",
    "            if check (s,step):\n",
    "                break\n",
    "            s = s - num2\n",
    "            if s <= 0 :\n",
    "                return -1\n",
    "            step += 1\n",
    "        \n",
    "        return step\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for x in range(1, 100):\n",
    "            # x是操作数\n",
    "            num1 -= num2\n",
    "            if num1 < x:\n",
    "                return -1\n",
    "            if num1.bit_count() <= x:\n",
    "                return x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in range(1, 10 ** 9):\n",
    "            num1 -= num2\n",
    "            if num1 < k: return -1\n",
    "            if num1.bit_count() <= k: return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): \n",
    "                return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        N = 100\n",
    "        for j in range(N):\n",
    "            num = num1 - j * num2\n",
    "            # 一个二进制表示，我其实可以捏出一个j元表示 只要digit小于j\n",
    "            if num <= 0:\n",
    "                if num2 > 0:\n",
    "                    break\n",
    "                continue\n",
    "\n",
    "            bitCount =  num.bit_count()\n",
    "            # print(j, num,  bitCount)\n",
    "            if (bitCount < j and num != 1) or bitCount == j:\n",
    "                return j\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        # num1 - k * num2 = 2 ^ (i1) + 2 ^ (i2) + ... + 2 ^ (ik)\n",
    "        if num1 <= num2:\n",
    "            return -1\n",
    "        \n",
    "        def check(n: int) -> bool:\n",
    "            res= num1 - n * num2\n",
    "            if res <= 0:\n",
    "                return False\n",
    "            if res.bit_count() <= n <= res:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        for i in range(1, 61):\n",
    "            if check(i):\n",
    "                return i\n",
    "        return -1\n",
    "        # left, right = 1, 60\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "        #     print(left, right, mid, check(mid))\n",
    "        #     if check(mid):\n",
    "        #         right = mid - 1\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "        # return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        def countBits(num):\n",
    "            count = 0\n",
    "            while num > 0:\n",
    "                count += (num % 2)\n",
    "                num = num // 2\n",
    "            return count\n",
    "\n",
    "        if num2 >= num1:\n",
    "            return -1\n",
    "\n",
    "        for step in range(101):\n",
    "            diff = num1 - step * num2\n",
    "            bits = countBits(diff)\n",
    "\n",
    "            if bits <= step and step <= diff:\n",
    "                return step\n",
    "\n",
    "        return -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2*k\n",
    "            if x<k: return -1\n",
    "            if k >= x.bit_count():return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        while True:\n",
    "            count += 1\n",
    "            tmp = num1 - count * num2\n",
    "            if tmp <= 0:\n",
    "                return -1\n",
    "            k = 0\n",
    "            while tmp > 0:\n",
    "                k += tmp & 1\n",
    "                tmp = tmp >> 1\n",
    "            if count == k or (count > k and (num1 - count * num2) >= count):\n",
    "                return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        def getOnes(x):\n",
    "            mincnt = 0\n",
    "            maxcnt = 0\n",
    "            k = 0\n",
    "            while(x > 0):\n",
    "                mincnt += x % 2\n",
    "                if(x % 2 == 1):\n",
    "                    maxcnt += 2**k\n",
    "                x = x // 2\n",
    "                k += 1\n",
    "            return mincnt, maxcnt\n",
    "        k = 1\n",
    "        while(num1 - k * num2 > 0):\n",
    "            mincnt, maxcnt = getOnes(num1 - k * num2)\n",
    "            if(mincnt <= k <= maxcnt):\n",
    "                return k\n",
    "            k += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        i = 0\n",
    "        while (num1 := num1 - num2) > i:\n",
    "            if num1.bit_count() <= (i := i+1):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in range(1,100) :\n",
    "            x=num1-num2*k\n",
    "            if x<k : return -1\n",
    "            if k>=x.bit_count() :\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for i in range(60):\n",
    "            num = num1 - i * num2\n",
    "            if num <= 0: break\n",
    "            if num >= i and num.bit_count() <= i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for i in range(64):\n",
    "            x=num1-num2*i \n",
    "            if i > x:\n",
    "                return -1\n",
    "            if i >= x.bit_count():\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        i = 0\n",
    "        while 1:\n",
    "            i = i + 1\n",
    "            cur = num1 - i*num2\n",
    "            if cur < i:\n",
    "                return -1\n",
    "            elif cur.bit_count() <= i:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k\n",
    "'''\n",
    "作者：灵茶山艾府\n",
    "链接：https://leetcode.cn/problems/minimum-operations-to-make-the-integer-zero/solutions/2319632/mei-ju-da-an-pythonjavacgo-by-endlessche-t4co/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k\n",
    "'''\n",
    "作者：灵茶山艾府\n",
    "链接：https://leetcode.cn/problems/minimum-operations-to-make-the-integer-zero/solutions/2319632/mei-ju-da-an-pythonjavacgo-by-endlessche-t4co/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        #         1100\n",
    "        #        1___1_1_1_1\n",
    "        #          1  1  1 1\n",
    "        #           11 \n",
    "        #            1  \n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k:\n",
    "                return -1\n",
    "            if k >= x.bit_count():\n",
    "                return k                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        start = num1\n",
    "        for i in range(1,61):\n",
    "            start -= num2\n",
    "            if start < i:return -1\n",
    "            cnt = bin(start).count('1')\n",
    "            if cnt <= i:return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        k = 1\n",
    "        while 1:\n",
    "            num1 -= num2\n",
    "            if num1 < k: return -1\n",
    "\n",
    "            print(k,num1, bin(num1)[2:])\n",
    "\n",
    "            if num1.bit_count() <= k: return k\n",
    "            k += 1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        if num1 <= num2:\n",
    "            return -1\n",
    "        if num2 == 0:\n",
    "            return bin(num1).count('1')\n",
    "        ret = 1\n",
    "        while True:\n",
    "            if num1 - ret * num2 < ret:\n",
    "                return -1\n",
    "            if bin(num1 - ret * num2).count('1') <= ret:\n",
    "                return ret\n",
    "            ret += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\r\n",
    "        if num1 == 0:\r\n",
    "            return 0 \r\n",
    "        for i in range(35):\r\n",
    "            num = num1 - num2 * i \r\n",
    "            if num > 0 and num.bit_count() <= i <= num:\r\n",
    "                return i\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        while num1 > num2:\n",
    "            ans += 1\n",
    "            num1 -= num2\n",
    "            t = num1.bit_count()\n",
    "            if t <= ans and ans <= num1:\n",
    "                return ans\n",
    "        return -1\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "\n",
    "        for k in count(1):\n",
    "\n",
    "            x = num1 - num2 * k\n",
    "\n",
    "            if x < k: return -1\n",
    "\n",
    "            if k >= x.bit_count(): return k\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x<k:\n",
    "                return -1\n",
    "            if k>=x.bit_count():\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 枚举答案\n",
    "    # https://www.bilibili.com/video/BV1du41187ZN/\n",
    "    # https://leetcode.cn/problems/minimum-operations-to-make-the-integer-zero/solutions/2319632/mei-ju-da-an-pythonjavacgo-by-endlessche-t4co/\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k:\n",
    "                return -1\n",
    "\n",
    "            if k >= x.bit_count():\n",
    "                return k\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        k=1\n",
    "        if num1<=num2: return -1\n",
    "        while True:\n",
    "            res=num1-k*num2\n",
    "            if res<=0: return -1\n",
    "            jkmin=res.bit_count()\n",
    "            jkmax=res\n",
    "            if jkmin<=k<=jkmax:\n",
    "                return k\n",
    "            k+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        k = 1 \n",
    "        while True:\n",
    "            diff = num1 - num2 * k    \n",
    "            if diff < k:\n",
    "                return - 1\n",
    "            if bin(diff).count('1') <= k:\n",
    "                return k\n",
    "            k += 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "\n",
    "\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k:\n",
    "                return -1\n",
    "            if x.bit_count() <= k:\n",
    "                return k\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        i = 1\n",
    "        while True:\n",
    "            num1 -= num2\n",
    "            if num1 < i:\n",
    "                return -1\n",
    "            if num1.bit_count() <= i:\n",
    "                return i\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while cnt < 10000:\n",
    "            cnt += 1\n",
    "            num1 -= num2\n",
    "            if num1 <= 0:\n",
    "                return -1\n",
    "            s = bin(num1)[2::]\n",
    "            if s.count('1') <= cnt and cnt <= num1:\n",
    "                return cnt\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, a: int, b: int) -> int:\n",
    "        def f(a):\n",
    "            s = bin(a)[2:]\n",
    "            n = len([j for j in s if j=='1'])\n",
    "            return n\n",
    "        if b==0:\n",
    "            return f(a)\n",
    "        else:\n",
    "            for k in range(1, 10**10):\n",
    "                if f(a - k*b) <= k <= (a - k*b):\n",
    "                    return k \n",
    "                if (a - k*b)<k:\n",
    "                    return -1 \n",
    "    \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\r\n",
    "        if num1 == 0:\r\n",
    "            return 0 \r\n",
    "        for i in range(40):\r\n",
    "            num = num1 - num2 * i \r\n",
    "            if num > 0 and num.bit_count() <= i <= num:\r\n",
    "                return i\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        if num1 == 0:\n",
    "            return 0\n",
    "        for i in range(1, 64):\n",
    "            x = num1 - i * num2 \n",
    "            if x <= 0:\n",
    "                break \n",
    "            #print(x, x.bit_count(), i)\n",
    "            if x.bit_count() <= i <= x:\n",
    "                return i \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        def getOnes(x):\n",
    "            mincnt = 0\n",
    "            while(x > 0):\n",
    "                mincnt += x % 2\n",
    "                x = x // 2\n",
    "            return mincnt\n",
    "        k = 1\n",
    "        while(num1 - k * num2 > 0):\n",
    "            mincnt = getOnes(num1 - k * num2)\n",
    "            if(mincnt <= k <= num1 - k * num2):\n",
    "                return k\n",
    "            k += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k:\n",
    "                return -1\n",
    "            if k >= x.bit_count():\n",
    "                return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        rst = -1\n",
    "        for k in range(1, 60):\n",
    "            num1 = num1 - num2\n",
    "            if num1 < k:\n",
    "                break\n",
    "            if bin(num1).count('1') <= k:\n",
    "                rst = k\n",
    "                break\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for k in count(1):\n",
    "            x = num1 - num2 * k\n",
    "            if x < k: return -1\n",
    "            if k >= x.bit_count(): return k\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cnt_1(n):\n",
    "    cnt = 0\n",
    "    while n > 0:\n",
    "        cnt += 1 & n\n",
    "        n = n >> 1\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        num_op = 0\n",
    "        while num1 > num2:\n",
    "            num1 -= num2\n",
    "            cnt = cnt_1(num1)\n",
    "            if cnt <= num_op + 1 <= num1:\n",
    "                return num_op + 1\n",
    "            num_op += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeTheIntegerZero(self, num1: int, num2: int) -> int:\n",
    "        for i in range(1,62):\n",
    "            num1-=num2\n",
    "            if num1<0:\n",
    "                return -1\n",
    "            if num1<i:\n",
    "                return -1\n",
    "            s=str(bin(num1)[2:])\n",
    "            print(i,num1,s)\n",
    "            c1=s.count(\"1\")\n",
    "            if c1<=i:\n",
    "                return i\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
